bzoj 2301 HAOI2011 Problem b

发表于 | 分类于 ， |
莫比乌斯反演

题目链接

BZOJ 2301 HAOI2011 Problem b

题解

利用函数f(x)表示x|(gcd(i,j))中ij的对数,那么原函数:

$?\dfrac{n}{k}?$最多只有$2\sqrt{n}$个取值,预处理$\mu(d)$ $O(\sqrt{n})$回答

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long LL;
const int maxn=50007;
inline int read() {
	int x=0;
    char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
int n,prime[maxn];
bool vis[maxn];long long mu[maxn];
void get_rj() {
    mu[1]=1;
    for(int i=2;i<=maxn-1;i++) {
        if(!vis[i]) prime[++prime[0]]=i,mu[i]=-1;
        for(int j=1;j<=prime[0]&&i*prime[j]<=maxn-1;j++) {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) {
                mu[i*prime[j]]=0;break;
            }
            mu[i*prime[j]]=-mu[i];
        }
    }
    for(int i=1;i<=maxn-1;i++) mu[i]+=mu[i-1];
}
LL calc(int n,int m,int k) {
    n/=k;m/=k;
    if(n>m) std::swap(n,m);
    LL ans=0;int next=0;
    for(int i=1;i<=n;i=next+1) {
        next=std::min(n/(n/i),m/(m/i));
        ans+=(mu[next]-mu[i-1])*(n/i)*(m/i);
    }
    return ans;
}
int main() {
    get_rj();
    int T=read();
    for(int a,b,c,d,k;T--;) {
        a=read();b=read();c=read();d=read();k=read();
        printf("%lld\n",calc(b,d,k)-calc(a-1,d,k)-calc(b,c-1,k)+calc(a-1,c-1,k));
    }
    return 0;
}